package com.ghxxzx.dagl.utils;

import org.apache.poi.ss.formula.functions.T;

import java.util.Comparator;

public class QuikSort {
/**
     * 快排
     * @param arr
     * @param low
     * @param high*/


    //arr 需要排序的数组
//low 开始时最左边的索引=0
//high 开始时最右边的索引=arr.length-1
    public static void quickSort(Integer[] arr, Integer low, Integer high, Comparator<Integer> comparator) {
        Integer i, j, t,temp;
        if (low > high) {
            return;
        }
        i = low;//左边监测索引
        j = high;//右边监测索引
        temp = arr[low]; //以左边为基数

        while (i < j) {
            //先看右边，依次往左递减
//            先从右往左找一个小于 基准位的数
//            当右边的哨兵位置所在的数>基准位的数 时
//            继续从右往左找（同时 j 索引-1）
//            找到后会跳出 while循环
            //>=升序
            //<=降序
            while (comparator.compare(temp,arr[j])>=0&& i < j) {
                j--;
            }
            //再看左边，依次往右递增
//            步骤和上面类似
            while (comparator.compare(arr[i],temp)>=0 && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
//                z、y 都是临时参数，用于存放 左右哨兵 所在位置的数据
                int z = arr[i];
                int y = arr[j];
//                左右哨兵 交换数据（互相持有对方的数据）
                arr[i] = y;
                arr[j] = z;
            }
        }
//        这时 跳出了 “while (i<j) {}” 循环
//        说明 i=j 左右在同一位置
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];//或 arr[low] = arr[j];
        arr[i] = temp;//或 arr[j] = temp;
//        i=j
//        这时  左半数组<(i或j所在索引的数)<右半数组
//        也就是说(i或j所在索引的数)已经确定排序位置， 所以就不用再排序了，
//         只要用相同的方法 分别处理  左右数组就可以了
        //递归调用左半数组
        quickSort(arr, low, j-1,(a,b)-> b.compareTo(a));
        //递归调用右半数组
        quickSort(arr, j+1, high,(a,b)-> b.compareTo(a));
    }
    //arr 需要排序的数组
//low 开始时最左边的索引=0
//high 开始时最右边的索引=arr.length-1
    public static void quickSort(String[] arr, Integer low, Integer high, Comparator<String> comparator) {
        Integer i, j;
        String temp;
        if (low > high) {
            return;
        }
        i = low;//左边监测索引
        j = high;//右边监测索引
        temp = arr[low]; //以左边为基数

        while (i < j) {
            //先看右边，依次往左递减
//            先从右往左找一个小于 基准位的数
//            当右边的哨兵位置所在的数>基准位的数 时
//            继续从右往左找（同时 j 索引-1）
//            找到后会跳出 while循环
            //>=升序
            //<=降序
            while (comparator.compare(temp,arr[j])<=0&& i < j) {
                j--;
            }
            //再看左边，依次往右递增
//            步骤和上面类似
            while (comparator.compare(arr[i],temp)<=0 && i < j) {
                i++;
            }
            //如果满足条件则交换
            if (i < j) {
//                z、y 都是临时参数，用于存放 左右哨兵 所在位置的数据
                String z = arr[i];
                String y = arr[j];
//                左右哨兵 交换数据（互相持有对方的数据）
                arr[i] = y;
                arr[j] = z;
            }
        }
//        这时 跳出了 “while (i<j) {}” 循环
//        说明 i=j 左右在同一位置
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];//或 arr[low] = arr[j];
        arr[i] = temp;//或 arr[j] = temp;
//        i=j
//        这时  左半数组<(i或j所在索引的数)<右半数组
//        也就是说(i或j所在索引的数)已经确定排序位置， 所以就不用再排序了，
//         只要用相同的方法 分别处理  左右数组就可以了
        //递归调用左半数组
        quickSort(arr, low, j-1,(a,b)-> b.compareTo(a));
        //递归调用右半数组
        quickSort(arr, j+1, high,(a,b)-> b.compareTo(a));
    }

    public static void selectionSort(int [] arr){
        for (int i = 0; i < arr.length-1; i++) {
            int a=arr[i];
            int b=i;
            for (int y = i+1; y < arr.length; y++) {
                if (arr[i]>=arr[y]){
                    arr[i]=arr[y];
                    b=y;
                }
            }
            arr[i] = arr[b];
            arr[b]=a;
        }
    }
/*    public static void main(String[] args) {
//        Integer[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19,10};
        String[] arr = {"刘备","关羽","张飞","曹操","司马懿"};
//        String[] arr = {"1","5","2"};
        quickSort(arr, 0, arr.length-1,(a,b)-> b.compareTo(a));
        for (String i : arr) {
            System.out.println(i);
        }
//        selectionSort(arr);
//        for (int i : arr) {
//            System.out.println(i);
//        }
    }*/
}
